#include "mylib.h"
#include <stdlib.h>
#define N 20

int BinarySearch_Iterative(int* array, int len, int key)
{
    int low = 0;
    int high = len-1;
    while (high >= low) {
        int mid = low + (high-low)/2;
        if (key == array[mid]) {
            return mid;
        }
        else if (key > array[mid]) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    return -1;
}

//@tailcall
int BinarySearch_Recursive(int* array, int low, int high, int key)
{
    if (high < low) {
        return -1;
    }
    int mid = low + (high-low)/2;
    if (key == array[mid]) {
        return mid;
    }
    else if (key > array[mid]) {
        return BinarySearch_Recursive(array, mid+1, high, key);
    }
    else
        return BinarySearch_Recursive(array, low, high-1, key);
}

int main()
{
    /*
	long int i = 100000000000000000;
	printf("%u\n", (unsigned)i);
	*/

	int* bar = (int*)malloc(N*sizeof(int));
	int i = 0;
	unsigned int seed = (unsigned)time(NULL);
	srand(seed);
	for (i=0; i<N; i++)	
		bar[i] = rand()%100;
	sortInt(bar, N);
	//for (i=0; i<N; i++) printf("%d ", bar[i]);
    int bar2[N] = {1, 14, 25, 28, 33, 33, 37, 47, 48, 56, 59, 61, 71, 71, 79, 82, 82, 85, 97, 98};
    for (i=0; i<N; i++) {
        //int pos = BinarySearch_Iterative(bar2, N, bar2[i]);
        int pos = BinarySearch_Recursive(bar2, 0, N-1, bar2[i]);
        printf("%d\n", pos);
    }
	free(bar);
	return 0;
}